package subject_set.offer100;

import java.util.HashSet;
import java.util.Set;

/**
 * @author haomin
 * @date 2022/10/20 15:33
 **/
public class Offer38 {
    class Solution {
        Set<String> set = new HashSet<>();
        public String[] permutation(String s) {
            char[] ch = s.toCharArray();
            boolean[] flag = new boolean[ch.length];
            dfs(ch, flag, new StringBuffer());
            return set.toArray(new String[0]);
        }
        private void dfs(char[] ch, boolean[] flag, StringBuffer sb){
            if(sb.length() == ch.length) {
                set.add(sb.toString());
                return;
            }
            for(int i = 0; i < ch.length; ++i){
                if(flag[i]) continue;
                sb.append(ch[i]); flag[i] = true;
                dfs(ch, flag, sb);
                sb.deleteCharAt(sb.length()-1); flag[i] = false;
            }
        }
    }
}